package MiddlePractice;

import java.util.HashSet;
import java.util.Set;

public class Demo128 {
//	128. 最长连续序列
//	给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
//
//	请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
	
	public int longestConsecutive(int[] nums) {
		
		//set去重
		Set<Integer> numSet = new HashSet<>();
		
		for(int num : nums) {
			numSet.add(num);
		}
		
		int maxLen = 0;
		
		//O(n)算法思路
		for(int num : numSet) {	//找到一个不存在前驱的数，从这个数开始找后继  这个数必定是连续子序列的开头
			if(!numSet.contains(num - 1)) {
				int curNum = num;
				int curLen = 1;
				
				while(numSet.contains(curNum + 1)) {	//只要后继存在  我们就一直找
					curNum = curNum + 1;
					curLen ++;
				}
				
				maxLen = Math.max(curLen, maxLen);
			}
			//num找后继的操作结束 
			//因为进入for循环之前  会判断数字有没有前驱在HashSet里面  所以while里面访问过的数字  在for里面一定不会访问第二遍
			//所以看似有两个循环嵌套  但是算法是On的
		}
		
		return maxLen;
		
    }

}
